<!DOCTYPE html>
<html lang="en">
<head>
    <meta charset="UTF-8">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <title>First Missing Positive Visualization</title>
    <script src="https://cdn.tailwindcss.com"></script>
    <script src="https://cdnjs.cloudflare.com/ajax/libs/three.js/r128/three.min.js"></script>
    <style>
        .array-cell {
            transition: all 0.5s ease;
            transform-style: preserve-3d;
        }
        .array-cell.flip {
            transform: rotateY(180deg);
        }
        .highlight {
            box-shadow: 0 0 15px 5px rgba(59, 130, 246, 0.7);
            transform: translateY(-5px) scale(1.05);
        }
        .current {
            box-shadow: 0 0 15px 5px rgba(16, 185, 129, 0.7);
        }
        .found {
            box-shadow: 0 0 15px 5px rgba(245, 158, 11, 0.7);
        }
        .result {
            box-shadow: 0 0 20px 10px rgba(220, 38, 38, 0.7);
            animation: pulse 1.5s infinite;
        }
        @keyframes pulse {
            0% { transform: scale(1); }
            50% { transform: scale(1.1); }
            100% { transform: scale(1); }
        }
        #canvas-container {
            width: 100%;
            height: 300px;
            position: relative;
        }
        #info-panel {
            transition: all 0.3s ease;
        }
    </style>
</head>
<body class="bg-gray-100 min-h-screen">
    <div class="container mx-auto px-4 py-8">
        <h1 class="text-3xl font-bold text-center text-blue-800 mb-6">First Missing Positive Integer Visualization</h1>
        
        <div class="bg-white rounded-xl shadow-lg p-6 mb-8">
            <div class="flex flex-col md:flex-row gap-8">
                <div class="flex-1">
                    <h2 class="text-xl font-semibold text-gray-800 mb-4">Algorithm Steps</h2>
                    <div id="info-panel" class="bg-blue-50 p-4 rounded-lg mb-4">
                        <p class="text-blue-800 font-medium">Initializing visualization...</p>
                    </div>
                    
                    <div class="flex justify-center mb-6">
                        <div class="flex flex-wrap gap-2" id="original-array"></div>
                    </div>
                    
                    <div class="mb-6">
                        <h3 class="text-lg font-medium text-gray-700 mb-2">Processing Array</h3>
                        <div class="flex flex-wrap gap-2" id="processing-array"></div>
                    </div>
                    
                    <div class="mb-6">
                        <h3 class="text-lg font-medium text-gray-700 mb-2">Result Array</h3>
                        <div class="flex flex-wrap gap-2" id="result-array"></div>
                    </div>
                    
                    <div class="bg-green-50 p-4 rounded-lg hidden" id="result-container">
                        <h3 class="text-lg font-medium text-green-800 mb-1">First Missing Positive:</h3>
                        <div class="text-2xl font-bold text-green-600" id="result-value"></div>
                    </div>
                </div>
                
                <div class="flex-1">
                    <div id="canvas-container"></div>
                    <div class="mt-4 text-center text-sm text-gray-600">
                        <p>3D visualization of the array processing</p>
                    </div>
                </div>
            </div>
            
            <div class="mt-6 flex flex-wrap justify-center gap-4">
                <button id="start-btn" class="px-4 py-2 bg-blue-600 text-white rounded-lg hover:bg-blue-700 transition flex items-center gap-2">
                    <svg xmlns="http://www.w3.org/2000/svg" class="h-5 w-5" viewBox="0 0 20 20" fill="currentColor">
                        <path fill-rule="evenodd" d="M10 18a8 8 0 100-16 8 8 0 000 16zM9.555 7.168A1 1 0 008 8v4a1 1 0 001.555.832l3-2a1 1 0 000-1.664l-3-2z" clip-rule="evenodd" />
                    </svg>
                    Start
                </button>
                <button id="pause-btn" class="px-4 py-2 bg-yellow-500 text-white rounded-lg hover:bg-yellow-600 transition flex items-center gap-2" disabled>
                    <svg xmlns="http://www.w3.org/2000/svg" class="h-5 w-5" viewBox="0 0 20 20" fill="currentColor">
                        <path fill-rule="evenodd" d="M18 10a8 8 0 11-16 0 8 8 0 0116 0zM7 8a1 1 0 012 0v4a1 1 0 11-2 0V8zm5-1a1 1 0 00-1 1v4a1 1 0 102 0V8a1 1 0 00-1-1z" clip-rule="evenodd" />
                    </svg>
                    Pause
                </button>
                <button id="reset-btn" class="px-4 py-2 bg-red-600 text-white rounded-lg hover:bg-red-700 transition flex items-center gap-2">
                    <svg xmlns="http://www.w3.org/2000/svg" class="h-5 w-5" viewBox="0 0 20 20" fill="currentColor">
                        <path fill-rule="evenodd" d="M4 2a1 1 0 011 1v2.101a7.002 7.002 0 0111.601 2.566 1 1 0 11-1.885.666A5.002 5.002 0 005.999 7H9a1 1 0 010 2H4a1 1 0 01-1-1V3a1 1 0 011-1zm.008 9.057a1 1 0 011.276.61A5.002 5.002 0 0014.001 13H11a1 1 0 110-2h5a1 1 0 011 1v5a1 1 0 11-2 0v-2.101a7.002 7.002 0 01-11.601-2.566 1 1 0 01.61-1.276z" clip-rule="evenodd" />
                    </svg>
                    Reset
                </button>
                
                <div class="flex items-center gap-2">
                    <span class="text-gray-700">Speed:</span>
                    <input type="range" id="speed-control" min="100" max="2000" value="800" class="w-32">
                    <span id="speed-value" class="text-gray-700">Normal</span>
                </div>
            </div>
        </div>
        
        <div class="bg-white rounded-xl shadow-lg p-6">
            <h2 class="text-xl font-semibold text-gray-800 mb-4">Algorithm Explanation</h2>
            <div class="prose max-w-none">
                <p>This algorithm finds the smallest missing positive integer in an unsorted array.</p>
                <ol class="list-decimal pl-5 space-y-2">
                    <li>First, we remove any zeros from the array (if present).</li>
                    <li>We create a result array initialized with zeros, with length equal to the input array length + 1.</li>
                    <li>We iterate through each number in the input array:
                        <ul class="list-disc pl-5 mt-1">
                            <li>If the number is positive and within the bounds of the array length, we mark its position in the result array.</li>
                        </ul>
                    </li>
                    <li>Finally, we scan the result array to find the first index that still contains zero - this index + 1 is our first missing positive integer.</li>
                </ol>
                <p class="mt-4">The visualization shows each step of this process with animations to help understand how the algorithm works.</p>
            </div>
        </div>
    </div>

    <script>
        // Sample input array
        const nums = [1, 2, 6, 3, 5, 4];
        let animationSpeed = 800;
        let animationInterval;
        let currentStep = 0;
        let isPaused = false;
        let isRunning = false;
        
        // Initialize the visualization
        document.addEventListener('DOMContentLoaded', function() {
            initOriginalArray();
            initResultArray();
            init3DVisualization();
            setupControls();
        });
        
        function initOriginalArray() {
            const container = document.getElementById('original-array');
            container.innerHTML = '';
            
            nums.forEach((num, index) => {
                const cell = document.createElement('div');
                cell.className = 'array-cell w-12 h-12 flex items-center justify-center bg-blue-100 border-2 border-blue-300 rounded-lg font-bold text-blue-800';
                cell.textContent = num;
                cell.dataset.index = index;
                cell.dataset.value = num;
                container.appendChild(cell);
            });
            
            updateInfoPanel('Initial array: ' + nums.join(', '));
        }
        
        function initResultArray() {
            const container = document.getElementById('result-array');
            container.innerHTML = '';
            
            // Create array with length nums.length + 1 (0 to n)
            for (let i = 0; i <= nums.length; i++) {
                const cell = document.createElement('div');
                cell.className = 'array-cell w-12 h-12 flex items-center justify-center bg-gray-100 border-2 border-gray-300 rounded-lg font-bold text-gray-800';
                cell.textContent = '0';
                cell.dataset.index = i;
                cell.dataset.value = '0';
                container.appendChild(cell);
            }
        }
        
        function init3DVisualization() {
            const container = document.getElementById('canvas-container');
            
            // Set up Three.js scene
            const scene = new THREE.Scene();
            const camera = new THREE.PerspectiveCamera(75, container.clientWidth / 300, 0.1, 1000);
            const renderer = new THREE.WebGLRenderer({ antialias: true, alpha: true });
            
            renderer.setSize(container.clientWidth, 300);
            container.appendChild(renderer.domElement);
            
            // Add lights
            const ambientLight = new THREE.AmbientLight(0x404040);
            scene.add(ambientLight);
            
            const directionalLight = new THREE.DirectionalLight(0xffffff, 0.8);
            directionalLight.position.set(1, 1, 1);
            scene.add(directionalLight);
            
            // Position camera
            camera.position.z = 10;
            camera.position.y = 3;
            camera.lookAt(0, 0, 0);
            
            // Create array elements
            const boxes = [];
            const boxSize = 0.8;
            const gap = 0.2;
            
            for (let i = 0; i <= nums.length; i++) {
                const geometry = new THREE.BoxGeometry(boxSize, boxSize, boxSize);
                const material = new THREE.MeshPhongMaterial({ 
                    color: 0xdddddd,
                    transparent: true,
                    opacity: 0.8
                });
                const box = new THREE.Mesh(geometry, material);
                
                box.position.x = i * (boxSize + gap) - (nums.length * (boxSize + gap)) / 2;
                box.position.y = 0;
                box.userData.index = i;
                box.userData.value = 0;
                
                scene.add(box);
                boxes.push(box);
                
                // Add text label
                const loader = new THREE.TextureLoader();
                const canvas = document.createElement('canvas');
                canvas.width = 64;
                canvas.height = 64;
                const context = canvas.getContext('2d');
                context.fillStyle = '#000000';
                context.font = 'Bold 24px Arial';
                context.textAlign = 'center';
                context.textBaseline = 'middle';
                context.fillText('0', 32, 32);
                
                const texture = new THREE.CanvasTexture(canvas);
                const labelMaterial = new THREE.MeshBasicMaterial({ 
                    map: texture,
                    transparent: true,
                    side: THREE.DoubleSide
                });
                const labelGeometry = new THREE.PlaneGeometry(boxSize * 0.8, boxSize * 0.8);
                const label = new THREE.Mesh(labelGeometry, labelMaterial);
                label.position.copy(box.position);
                label.position.z = boxSize / 2 + 0.01;
                scene.add(label);
                box.userData.label = label;
            }
            
            // Animation loop
            function animate() {
                requestAnimationFrame(animate);
                renderer.render(scene, camera);
            }
            animate();
            
            // Handle window resize
            window.addEventListener('resize', function() {
                camera.aspect = container.clientWidth / 300;
                camera.updateProjectionMatrix();
                renderer.setSize(container.clientWidth, 300);
            });
            
            // Store scene for later use
            window.threeScene = {
                scene,
                camera,
                renderer,
                boxes
            };
        }
        
        function setupControls() {
            // Speed control
            const speedControl = document.getElementById('speed-control');
            const speedValue = document.getElementById('speed-value');
            
            speedControl.addEventListener('input', function() {
                animationSpeed = 2100 - this.value; // Invert so right is faster
                
                if (animationSpeed > 1500) speedValue.textContent = 'Slow';
                else if (animationSpeed > 800) speedValue.textContent = 'Normal';
                else if (animationSpeed > 400) speedValue.textContent = 'Fast';
                else speedValue.textContent = 'Very Fast';
                
                if (isRunning && !isPaused) {
                    clearInterval(animationInterval);
                    startAnimation();
                }
            });
            
            // Start button
            document.getElementById('start-btn').addEventListener('click', function() {
                if (!isRunning) {
                    startAnimation();
                } else if (isPaused) {
                    resumeAnimation();
                }
            });
            
            // Pause button
            document.getElementById('pause-btn').addEventListener('click', function() {
                if (isRunning && !isPaused) {
                    pauseAnimation();
                }
            });
            
            // Reset button
            document.getElementById('reset-btn').addEventListener('click', function() {
                resetAnimation();
            });
        }
        
        function startAnimation() {
            isRunning = true;
            isPaused = false;
            currentStep = 0;
            
            document.getElementById('start-btn').disabled = true;
            document.getElementById('pause-btn').disabled = false;
            document.getElementById('reset-btn').disabled = true;
            
            // Reset arrays
            initOriginalArray();
            initResultArray();
            
            // Reset 3D visualization
            const { boxes } = window.threeScene;
            boxes.forEach(box => {
                box.material.color.setHex(0xdddddd);
                box.userData.value = 0;
                
                // Update label
                const canvas = box.userData.label.material.map.image;
                const context = canvas.getContext('2d');
                context.clearRect(0, 0, canvas.width, canvas.height);
                context.fillStyle = '#000000';
                context.font = 'Bold 24px Arial';
                context.textAlign = 'center';
                context.textBaseline = 'middle';
                context.fillText('0', 32, 32);
                box.userData.label.material.map.needsUpdate = true;
            });
            
            document.getElementById('result-container').classList.add('hidden');
            
            animationInterval = setInterval(executeStep, animationSpeed);
            updateInfoPanel('Starting algorithm...');
        }
        
        function pauseAnimation() {
            isPaused = true;
            clearInterval(animationInterval);
            
            document.getElementById('start-btn').disabled = false;
            document.getElementById('pause-btn').disabled = true;
            document.getElementById('reset-btn').disabled = false;
            
            updateInfoPanel('Algorithm paused at step ' + (currentStep + 1));
        }
        
        function resumeAnimation() {
            isPaused = false;
            document.getElementById('start-btn').disabled = true;
            document.getElementById('pause-btn').disabled = false;
            document.getElementById('reset-btn').disabled = true;
            
            animationInterval = setInterval(executeStep, animationSpeed);
            updateInfoPanel('Resuming algorithm...');
        }
        
        function resetAnimation() {
            clearInterval(animationInterval);
            isRunning = false;
            isPaused = false;
            currentStep = 0;
            
            document.getElementById('start-btn').disabled = false;
            document.getElementById('pause-btn').disabled = true;
            document.getElementById('reset-btn').disabled = false;
            
            initOriginalArray();
            initResultArray();
            
            // Reset 3D visualization
            const { boxes } = window.threeScene;
            boxes.forEach(box => {
                box.material.color.setHex(0xdddddd);
                box.userData.value = 0;
                
                // Update label
                const canvas = box.userData.label.material.map.image;
                const context = canvas.getContext('2d');
                context.clearRect(0, 0, canvas.width, canvas.height);
                context.fillStyle = '#000000';
                context.font = 'Bold 24px Arial';
                context.textAlign = 'center';
                context.textBaseline = 'middle';
                context.fillText('0', 32, 32);
                box.userData.label.material.map.needsUpdate = true;
            });
            
            document.getElementById('result-container').classList.add('hidden');
            updateInfoPanel('Visualization reset. Click Start to begin.');
        }
        
        function executeStep() {
            const steps = [
                // Step 0: Highlight original array
                () => {
                    highlightOriginalArray();
                    updateInfoPanel('Original array: ' + nums.join(', '));
                },
                
                // Step 1: Remove zeros (none in our example)
                () => {
                    updateInfoPanel('Checking for zeros to remove (none in this array)');
                },
                
                // Step 2: Initialize result array
                () => {
                    updateInfoPanel('Initializing result array with zeros');
                    highlightResultArray();
                },
                
                // Steps 3-8: Process each element in the original array
                ...nums.map((num, i) => () => {
                    processArrayElement(i, num);
                    updateInfoPanel(`Processing element ${i}: ${num}`);
                }),
                
                // Step 9: Find first missing positive
                () => {
                    findFirstMissingPositive();
                    updateInfoPanel('Scanning result array for first missing positive');
                },
                
                // Step 10: Show result
                () => {
                    showResult();
                    updateInfoPanel('Algorithm complete! First missing positive found.');
                    clearInterval(animationInterval);
                    isRunning = false;
                    document.getElementById('start-btn').disabled = false;
                    document.getElementById('pause-btn').disabled = true;
                    document.getElementById('reset-btn').disabled = false;
                }
            ];
            
            if (currentStep < steps.length) {
                steps[currentStep]();
                currentStep++;
            }
        }
        
        function highlightOriginalArray() {
            const cells = document.querySelectorAll('#original-array .array-cell');
            cells.forEach(cell => {
                cell.classList.add('highlight');
                
                setTimeout(() => {
                    cell.classList.remove('highlight');
                }, animationSpeed / 2);
            });
        }
        
        function highlightResultArray() {
            const cells = document.querySelectorAll('#result-array .array-cell');
            cells.forEach(cell => {
                cell.classList.add('highlight');
                
                setTimeout(() => {
                    cell.classList.remove('highlight');
                }, animationSpeed / 2);
            });
        }
        
        function processArrayElement(index, value) {
            // Highlight current element in original array
            const originalCells = document.querySelectorAll('#original-array .array-cell');
            originalCells[index].classList.add('current');
            
            // Highlight corresponding position in result array if valid
            if (value > 0 && value <= nums.length) {
                const resultCells = document.querySelectorAll('#result-array .array-cell');
                const targetIndex = value - 1;
                
                setTimeout(() => {
                    // Update 2D visualization
                    resultCells[targetIndex].textContent = value;
                    resultCells[targetIndex].dataset.value = value;
                    resultCells[targetIndex].classList.add('found');
                    resultCells[targetIndex].classList.remove('bg-gray-100', 'text-gray-800');
                    resultCells[targetIndex].classList.add('bg-yellow-100', 'text-yellow-800');
                    
                    // Update 3D visualization
                    const { boxes } = window.threeScene;
                    boxes[targetIndex].material.color.setHex(0xffdd59);
                    boxes[targetIndex].userData.value = value;
                    
                    // Update label
                    const canvas = boxes[targetIndex].userData.label.material.map.image;
                    const context = canvas.getContext('2d');
                    context.clearRect(0, 0, canvas.width, canvas.height);
                    context.fillStyle = '#000000';
                    context.font = 'Bold 24px Arial';
                    context.textAlign = 'center';
                    context.textBaseline = 'middle';
                    context.fillText(value.toString(), 32, 32);
                    boxes[targetIndex].userData.label.material.map.needsUpdate = true;
                    
                    // Flip animation
                    resultCells[targetIndex].classList.add('flip');
                    setTimeout(() => {
                        resultCells[targetIndex].classList.remove('flip');
                    }, 500);
                    
                    // Highlight the connection
                    originalCells[index].classList.add('highlight');
                    setTimeout(() => {
                        originalCells[index].classList.remove('highlight');
                    }, animationSpeed / 2);
                }, animationSpeed / 2);
            }
            
            setTimeout(() => {
                originalCells[index].classList.remove('current');
            }, animationSpeed);
        }
        
        function findFirstMissingPositive() {
            const resultCells = document.querySelectorAll('#result-array .array-cell');
            const { boxes } = window.threeScene;
            
            // Find first zero in result array
            let missingIndex = -1;
            for (let i = 0; i < resultCells.length; i++) {
                if (resultCells[i].dataset.value === '0') {
                    missingIndex = i;
                    break;
                }
            }
            
            if (missingIndex !== -1) {
                setTimeout(() => {
                    // Highlight in 2D
                    resultCells[missingIndex].classList.add('result');
                    
                    // Highlight in 3D
                    boxes[missingIndex].material.color.setHex(0xff5e57);
                    
                    // Pulse animation
                    let scale = 1;
                    const pulseInterval = setInterval(() => {
                        scale = scale === 1 ? 1.2 : 1;
                        boxes[missingIndex].scale.set(scale, scale, scale);
                    }, 300);
                    
                    // Store interval to clear later
                    boxes[missingIndex].userData.pulseInterval = pulseInterval;
                }, animationSpeed / 2);
            }
            
            return missingIndex + 1;
        }
        
        function showResult() {
            const missingPositive = findFirstMissingPositive();
            const resultContainer = document.getElementById('result-container');
            const resultValue = document.getElementById('result-value');
            
            resultValue.textContent = missingPositive;
            resultContainer.classList.remove('hidden');
        }
        
        function updateInfoPanel(message) {
            const infoPanel = document.getElementById('info-panel');
            infoPanel.innerHTML = `<p class="text-blue-800 font-medium">${message}</p>`;
        }
    </script>
</body>
</html>